/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 邓大帅
 * Date: 2023-02-19
 * Time: 17:17
 */
public class Test1 {
    //后序遍历
    class Solution {
        public List<Integer> postorderTraversal(TreeNode root) {
            // 如果是空树，直接返回
            List<Integer> ret = new ArrayList<>();
            if(null == root){
                return ret;
            }
            TreeNode cur = root;
            TreeNode prev = null;  // 记录刚刚过节点的前一个
            Stack<TreeNode> s = new Stack<>();
            while(null != cur || !s.empty()){
                // 找以cur为根的最左侧节点，并保存其所经路径中所有的节点
                while(cur != null){
                    s.push(cur);
                    cur = cur.left;
                }
                // 此处不能直接遍历根，根节点的右子树遍历完成之后才可以遍历根
                TreeNode top = s.peek();
                // 如果根节点的右子树是空，或者右子树已经遍历过了
                if(top.right == null || top.right == prev){
                    ret.add(top.val);
                    prev = top;
                    s.pop();
                }
                else
                {
                    // 如果top的右子树存在，并且没有遍历过，将其右子树当成新树遍历
                    cur = top.right;
                }
            }
            return ret;
        }
    }
    //中序遍历
    class Solution {
        public List<Integer> inorderTraversal(TreeNode root) {
            List<Integer> ret = new ArrayList<>();
            // 空树直接返回
            if(null == root){
                return ret;
            }
            Stack<TreeNode> s = new Stack<>();
            TreeNode cur = root;
            while(null != cur || !s.empty()){
                // 沿这cur一直往左侧走，找到该条路径中最左侧的节点，并保存其所经路径中的所有节点
                while(null != cur){
                    s.push(cur);
                    cur = cur.left;
                }
                // 获取根节点，直接遍历，因为其左侧是空树
                cur = s.peek();
                s.pop();
                ret.add(cur.val);
                // cur的左子树已经遍历，cur已经遍历，剩余其右子树没有遍历，
                // 将其右子树当成一棵新的树进行遍历
                cur = cur.right;
            }
            return ret;
        }
    }
    //前序遍历
    class Solution {
        public List<Integer> preorderTraversal(TreeNode root) {
            List<Integer> ret = new ArrayList<>();
            Stack<TreeNode> s = new Stack<>();
            TreeNode cur = root;
            while(null != cur || !s.empty())
            {
                // 每次循环表示要开始访问一颗树了，先将一颗树的左路节点都入栈并访问节点
                // 剩余左路节点的右子树还没访问
                while(null != cur)
                {
                    ret.add(cur.val);
                    s.push(cur);
                    cur = cur.left;
                }


                // 取栈中的节点依次访问左路节点的右子树
                cur = s.pop();
                cur = cur.right;
            }
            return ret;
        }
    }
}
